Many processors include a branch predictor that predicts which direction the program flow will take in the case of instructions known to cause possible flow changes, such as branch instructions. Branch prediction is useful as it enables instructions to be speculatively executed by the processor before the outcome of the branch instruction is known.
Branch instructions may be classified as conditional or indirect. Conditional branch instructions (branch instructions based on a constant value) require a binary decision as to whether the branch is taken or not-taken. Indirect branch instructions (branch instructions based on a variable) require an N-ary decision as to the target address where N is the number of possible target addresses.
Schemes for predicting the outcome of a conditional branch can be categorized into static and dynamic prediction schemes. Static prediction schemes typically base the prediction on a static value such as opcode or direction of the branch. Dynamic prediction schemes, on the other hand, take into account runtime behavior.
The most common dynamic branch prediction scheme is the two-level adaptive predictor scheme which makes branch predictions based on the history of branches executed during the current execution of the program. For example, a history of the last N outcomes (taken/not-taken) of previous conditional branch instructions, referred to as the taken/not-taken history, may be maintained. The history is then used to update a pattern history table (PHT) which has an entry for each possible pattern of the history. After a prediction is made the entry in the PHT corresponding to the current history pattern is updated with the prediction. Then the next time that history pattern appears the same prediction can be made.
Generally, the longer the history, the more accurate the prediction. However, as the history grows so does the PHT. In particular each bit added to the history doubles the size of the PHT. Accordingly, there is a desire to increase conditional branch prediction accuracy by using a longer history without significantly increasing the amount of information that has to be stored to make the prediction.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known branch predictors.